using System;
using System.Reflection;
using System.Collections;
using System.Diagnostics;
using System.Text;

namespace Meta
{
	/// <summary>
	/// Summary description for TypeLattice.
	/// </summary>
	public class TypeLattice {
		static Hashtable globalKnownMemberTable = new Hashtable();
		static Fluid packageKnownMemberTable = new NamespaceFluid(null);

		public static Type CheckKnownMember(string name) {
			object localTable = packageKnownMemberTable.Value;
			if (localTable!=null) {
				object probe = ((Hashtable)localTable)[name];
				if (probe!=null)
					return (Type)probe;
			}
			object gprobe = globalKnownMemberTable[name];
			if (gprobe!=null)
				return (Type)gprobe;
			else
				return null;
		}

		public static void DeclareKnownMember(Type type, string memberName) {
			if (packageKnownMemberTable.Value==null)
				packageKnownMemberTable.Value = new Hashtable();
			((Hashtable)(packageKnownMemberTable.Value))[memberName] = type;
		}

		public static void GlobalDeclareKnownMember(Type type, string memberName) {
			globalKnownMemberTable[memberName] = type;
		}

		public static void DeclareKnownType(Type t, IList exceptions) {
			foreach (MemberInfo m in t.GetMembers(BindingFlags.Public | BindingFlags.Instance)) {
				if (exceptions.Contains(m.Name) || m.DeclaringType!=t)
					continue;
				switch (m.MemberType) {
					case MemberTypes.Event:
					case MemberTypes.Field:
					case MemberTypes.Property:
						DeclareKnownMember(t, m.Name);
						break;

					case MemberTypes.Method:
						MethodInfo meth = (MethodInfo)m;
						if (!meth.IsSpecialName)
							DeclareKnownMember(t, m.Name);
						break;

					default:
						break;
				}
			}
		}

		public static void GlobalDeclareKnownType(Type t, IList exceptions) {
			foreach (MemberInfo m in t.GetMembers(BindingFlags.Public)) {
				if (exceptions.Contains(m.Name) || m.DeclaringType!=t)
					continue;
				switch (m.MemberType) {
					case MemberTypes.Event:
					case MemberTypes.Field:
					case MemberTypes.Property:
						GlobalDeclareKnownMember(t, m.Name);
						break;

					case MemberTypes.Method:
						MethodInfo meth = (MethodInfo)m;
						if (!meth.IsSpecialName)
							GlobalDeclareKnownMember(t, m.Name);
						break;

					default:
						break;
				}
			}
		}

		//
		// Sub is a subtype of or equivalent to super.
		//
		public static bool SubTypeInclusive(Type sub, Type super) {
			if (sub is LUBType)
				sub = ((LUBType)sub).Type;
			if (super is LUBType)
				super = ((LUBType)super).Type;
			if (sub==super)
				return true;
			return SubType(sub, super);
		}

		// Strict subtypes
		public static bool SubType(Type sub, Type super) {
			if (sub is LUBType)
				sub = ((LUBType)sub).Type;
			if (super is LUBType)
				super = ((LUBType)super).Type;
			if (super==typeof(object))
				return true;
			if (sub is ProcedureType && super==typeof(Procedure))
				return true;
			if (super.IsInterface) {
				if (super==typeof(IList) && (sub is ListOf || sub.IsArray))
					return true;
				Type[] interfaces = sub.GetInterfaces();
				if (interfaces==null)
					return false;
				foreach (Type interf in interfaces)
					if (interf==super)
						return true;
				return false;
			} else {
				if (super is PseudoType)
					return super.IsAssignableFrom(sub);
				return sub.IsSubclassOf(super);
			}
		}

		public static Type LUB(params Type[] types) {
			Type result=types[0];
			for (int i=1; i<types.Length; i++)
				result = LUB(result, types[i]);
			return result;
		}

#if notdef
		public static Type LUB(TypeVariable[] typeVars) {
			Type result=typeVars[0].type;
			for (int i=1; i<typeVars.Length; i++)
				result = LUB(result, typeVars[i].type);
			return result;
		}
#endif

		public static Type LUB(IList args) {
			Type result=null;
			for (int i=0; i<args.Count; i++) {
				if (result==null) {
					if (args[i]==null)
						continue;
					else if (args[i] is Type)
						result = (Type)args[i];
					else if (args[i] is TypeVariable) {
						TypeVariable v=(TypeVariable)args[i];
						if (v.Type!=null)
							result=v.Type;
					} else
						throw new ArgumentTypeException("type", args[i], typeof(Type));
				} else if (args[i] is Type)
					result = LUB(result, (Type)args[i]);
				else if (args[i] is TypeVariable) {
					TypeVariable v = (TypeVariable)args[i];
					if (v.Type!=null)
						result = LUB(result, v.Type);
				} else
					throw new ArgumentTypeException("type", args[i], typeof(Type));
			}
			return result;
		}

		public static Type LUB(Type a, Type b) {
			if (a==typeof(object) || b==typeof(object))
				return typeof(object);
			if (a.IsValueType || a is PseudoType || b is PseudoType)
				return ValueLUB(a, b);
			else if (a.IsInterface)
				return InterfaceLUB(b, a);
			else if (b.IsInterface)
				return InterfaceLUB(a, b);
			else 
				return RefLUB(a, b);
		}

		// i will always be an interface.
		// This is imprecise, since it won't handle the LUB of two interfaces that don't implement each other
		// but do both implement a third interface.
		static Type InterfaceLUB(Type a, Type i) {
			if (i==a)
				return i;
			Type[] intfs = a.GetInterfaces();
			if (intfs!=null) {
				foreach (Type intf in intfs)
					if (intf==i)
						return i;
			}
			intfs = a.GetInterfaces();
			if (intfs!=null) {
				foreach (Type intf in intfs)
					if (intf==a)
						return a;
			}
			return typeof(object);
		}

		// LUB of reference types
		static Type RefLUB(Type a, Type b) {
			while (true) {
				if (b==null)
					return typeof(object);
				if (a==b || a.IsSubclassOf(b))
					return b;
				else
					b = b.BaseType;
			}
		}

		// LUB of value types
		static Type  ValueLUB(Type a, Type b) {
			if (a==b)
				return a;
			if (a==null)
				return b;
			if (b==null)
				return a;
			if (IsIntegerType(a)) {
				if (IsIntegerType(b))
					return PseudoType.Integer;
				else if (IsNumericType(b) || b==PseudoType.Number)
					return PseudoType.Number;
			} else if (IsFloatType(a)) {
				if (IsFloatType(b))
					return PseudoType.Float;
				else if (IsIntegerType(a) || b==PseudoType.Number)
					return PseudoType.Number;
			} else if (a==PseudoType.Number && IsNumericType(b))
				return PseudoType.Number;
			else if (Is2DVectorTypeInclusive(a) || Is2DVectorTypeInclusive(b))
				return PseudoType.Vector2D;
			else if (IsVectorTypeInclusive(a) && IsVectorTypeInclusive(b))
				return PseudoType.Vector;
			else if (IsArithmeticTypeInclusive(a) && IsArithmeticTypeInclusive(b))
				return PseudoType.Arithmetic;

			return typeof(Object);
		}

		public static bool Is2DVectorTypeInclusive(Type t) {
			return VectorSpace.Is2DVectorType(t) || t==PseudoType.Vector2D;
		}

		public static bool IsVectorType(Type t) {
			return VectorSpace.IsVectorType(t) || t==PseudoType.Vector2D;
		}

		public static bool IsVectorTypeInclusive(Type t) {
			return VectorSpace.IsVectorType(t) || t==PseudoType.Vector2D || t==PseudoType.Vector;
		}

		public static bool IsArithmeticType(Type t) {
			return IsNumericType(t) || VectorSpace.IsVectorSpace(t) || t==PseudoType.Vector || t==PseudoType.Vector2D;
		}

		public static bool IsArithmeticTypeInclusive(Type t) {
			return IsNumericType(t) || VectorSpace.IsVectorSpace(t) || t==PseudoType.Arithmetic || t==PseudoType.Vector || t==PseudoType.Vector2D;
		}

		public static bool IsArithmetic(object o) {
			return IsArithmeticType(o.GetType());
		}

		public static bool IsIntegerType(Type t) {
			return t==typeof(Byte) || t==typeof(Int16) || t==typeof(Int32) ||t==typeof(Int64) || t==typeof(SByte) || t==typeof(UInt16) || t==typeof(UInt32) || t==typeof(UInt64) || t==PseudoType.Integer;
		}

		public static bool IsIntegralType(Type t) {
			return t==typeof(Byte) || t==typeof(Int16) || t==typeof(Int32) ||t==typeof(Int64) || t==typeof(SByte) || t==typeof(UInt16) || t==typeof(UInt32) || t==typeof(UInt64) || t==PseudoType.Integer
				|| t.IsEnum || t==typeof(System.Enum);
		}


		public static bool IsFloatType(Type t) {
			return t==typeof(Decimal) || t==typeof(double) || t==typeof(float) || t==PseudoType.Float || t==PseudoType.Float;
		}

		public static bool IsNumericType(Type t) {
			return IsFloatType(t) || IsIntegerType(t) || t==PseudoType.Number;
		}

		public static bool IsIntegerSuperType(Type t) {
			return t==PseudoType.Number || t==PseudoType.Arithmetic;
		}

		public static bool IsIntegralSuperType(Type t) {
			return t==PseudoType.Number || t==PseudoType.Arithmetic || t==PseudoType.Integral || t==typeof(System.Enum);
		}

		public static bool IsFloatSuperType(Type t) {
			return t==PseudoType.Number || t==PseudoType.Arithmetic;;
		}

		public static bool IsNumberSuperType(Type t) {
			return t==PseudoType.Arithmetic;
		}

		public static bool Is2DVectorSuperType(Type t) {
			return t==PseudoType.Arithmetic || t==PseudoType.Vector;
		}

		public static bool IsVectorSuperType(Type t) {
			return t==PseudoType.Arithmetic;
		}

		public static bool IsArithmeticSuperType(Type t) {
			return false;
		}

	}


	public class TypeWalker {
		public static Hashtable NameTypes(object x) {
			Hashtable h = new Hashtable();
			Hashtable result = new Hashtable();
			Walk(x, h);

			int counter = 0;
			foreach (DictionaryEntry e in h) {
				if ((int)e.Value>1)
					result[e.Key] = counter++;
			}
			return result;
		}

		static void Walk(object x, Hashtable h) {
			if (x is TypeVariable)
				Walk((TypeVariable)x, h);
			else if (x is SimpleProcedureType)
				Walk((SimpleProcedureType)x, h);
			else if (x is LUBType) {
				Walk((LUBType)x, h);
			} else if (x is ListOf) {
				Walk((ListOf)x, h);
			}
		}

		static void Walk(SimpleProcedureType s, Hashtable h) {
			foreach (TypeVariable a in s.argTypes)
				Walk(a, h);
			Walk(s.restArgType, h);
			Walk(s.resultType, h);
		}

		static void Walk(ListOf l, Hashtable h) {
			Walk(l.ItemType, h);
		}

		static void Walk(LUBType t, Hashtable h) {
			//t.Update();
			foreach (object o in t.bounds)
				Walk(o, h);
		}

		static void Walk(TypeVariable v, Hashtable h) {
			v = v.Representative;
			if (Touch(v, h))
				Walk(v.Type, h);
		}

		static bool Touch(TypeVariable t, Hashtable h) {
			if (h.ContainsKey(t)) {
				h[t] = (int)h[t]+1;
				return false;
			} else {
				h[t] = 1;
				return true;
			}
		}

		public static string Format(Type t, Hashtable h) {
			if (t==null)
				return "null";
			else if (t is IPrettyPrintableType)
				return ((IPrettyPrintableType)t).PrettyPrint(h);
			else
				return t.Name;
		}
	}

	public interface IPrettyPrintableType {
		string PrettyPrint(Hashtable h);
	}

	
	//
	// PseudoTypes are abstract classes that compensate
	// for the lack of inheritance in value types.  They let there
	// appear to be types called "Number", "Float", and "Integer".
	//
	public abstract class PseudoType : Type {
		public static readonly NumericPseudoType theIntegerType = new NumericPseudoType("Integer",
			new NumericPseudoType.TypePredicate(Meta.Utilities.IsInteger), new NumericPseudoType.SubTypePredicate(TypeLattice.IsIntegerType),
			new NumericPseudoType.SuperTypePredicate(TypeLattice.IsIntegerSuperType));
		public static readonly NumericPseudoType theIntegralType = new NumericPseudoType("Integral",
			new NumericPseudoType.TypePredicate(Meta.Utilities.IsIntegral), new NumericPseudoType.SubTypePredicate(TypeLattice.IsIntegralType),
			new NumericPseudoType.SuperTypePredicate(TypeLattice.IsIntegralSuperType));
		public static readonly NumericPseudoType theFloatType = new NumericPseudoType("Float",
			new NumericPseudoType.TypePredicate(Meta.Utilities.IsFloat), new NumericPseudoType.SubTypePredicate(TypeLattice.IsFloatType),
			new NumericPseudoType.SuperTypePredicate(TypeLattice.IsFloatSuperType));
		public static readonly NumericPseudoType theNumberType = new NumericPseudoType("Number",
			new NumericPseudoType.TypePredicate(Meta.Utilities.IsNumber), new NumericPseudoType.SubTypePredicate(TypeLattice.IsNumericType),
			new NumericPseudoType.SuperTypePredicate(TypeLattice.IsNumberSuperType));
		public static readonly NumericPseudoType theVector2DType = new NumericPseudoType("Vector2D", 
			new NumericPseudoType.TypePredicate(VectorSpace.Is2DVector), new NumericPseudoType.SubTypePredicate(VectorSpace.Is2DVectorType),
			new NumericPseudoType.SuperTypePredicate(TypeLattice.Is2DVectorSuperType));
		public static readonly NumericPseudoType theVectorType = new NumericPseudoType("Vector",
			new NumericPseudoType.TypePredicate(VectorSpace.IsVector), new NumericPseudoType.SubTypePredicate(TypeLattice.IsVectorTypeInclusive),
			new NumericPseudoType.SuperTypePredicate(TypeLattice.IsVectorSuperType));
		public static readonly NumericPseudoType theArithmeticType = new NumericPseudoType("ArithmeticType",
			new NumericPseudoType.TypePredicate(TypeLattice.IsArithmetic), new NumericPseudoType.SubTypePredicate(TypeLattice.IsArithmeticTypeInclusive),
			new NumericPseudoType.SuperTypePredicate(TypeLattice.IsArithmeticSuperType));

		public const string myNamespace = "Meta";

		public static Type Vector2D {
			get {
				return theVector2DType;
			}
		}
		public static Type Vector {
			get {
				return theVectorType;
			}
		}
		public static Type Arithmetic {
			get {
				return theArithmeticType;
			}
		}

		public static Type Integer {
			get {
				return theIntegerType;
			}
		}
		public static Type Float {
			get {
				return theFloatType;
			}
		}
		public static Type Number {
			get {
				return theNumberType;
			}
		}

		public static Type Integral {
			get {
				return theIntegralType;
			}
		}

		public override Guid GUID {
			get {
				return new Guid ();
			}
		}

		// Type info stuff
		public override Type BaseType {
			get {
				return typeof(System.Object);
			}
		}
		protected override TypeAttributes GetAttributeFlagsImpl() {
			return TypeAttributes.Abstract;
		}
		protected override bool IsArrayImpl() {
			return false;
		}
		protected override bool IsByRefImpl() {
			return true;
		}
		protected override bool IsCOMObjectImpl() {
			return false;
		}
		protected override bool IsPointerImpl() {
			return false;
		}
		protected override bool IsPrimitiveImpl() {
			return false;
		}
		public override RuntimeTypeHandle TypeHandle {
			get {
				return new RuntimeTypeHandle ();
			}
		}
		public override Type UnderlyingSystemType {
			get {
				return typeof(object);  // ???
			}
		}

		public override object InvokeMember(string name, BindingFlags invokeAttr, Binder binder, object target, object[] args, ParameterModifier[] modifiers, System.Globalization.CultureInfo culture, string[] namedParameters) {
			throw new MissingMemberException(FullName, name);
		}

		//
		// PseudoTypes aren't real classes, so none of the following operations make any sense.
		// However, we have to have implementations of them to get things to compile.
		//

		// Assembly stuff
		public override Assembly Assembly {
			get {
				return null;
			}
		}
		public override string AssemblyQualifiedName {
			get {
				return null;
			}
		}
		public override Module Module {
			get {
				return null;
			}
		}
		public override string Namespace {
			get {
				return myNamespace;
			}
		}

		// Attribute stuff
		public override object[] GetCustomAttributes(bool inherit) {
			return null;
		}
		public override object[] GetCustomAttributes(Type attributeType, bool inherit) {
			return null;
		}
		public override bool IsDefined(Type attributeType, bool inherit) {
			return false;
		}

		// Member stuff
		protected override ConstructorInfo GetConstructorImpl(BindingFlags bindingAttr, Binder binder, CallingConventions callConvention, Type[] types, ParameterModifier[] modifiers) {
			return typeof(object).GetConstructor(bindingAttr, binder, callConvention, types, modifiers);
		}
		public override ConstructorInfo[] GetConstructors(BindingFlags bindingAttr) {
			return null;
		}
		public override EventInfo GetEvent(string name, BindingFlags bindingAttr) {
			return null;
		}
		public override EventInfo[] GetEvents(BindingFlags bindingAttr) {
			return null;
		}
		public override FieldInfo GetField(string name, BindingFlags bindingAttr) {
			return null;
		}
		public override FieldInfo[] GetFields(BindingFlags bindingAttr) {
			return null;
		}
		public override MemberInfo[] GetMember(string name, BindingFlags bindingAttr) {
			return typeof(object).GetMember(name,bindingAttr);
		}
		public override MemberInfo[] GetMembers(BindingFlags bindingAttr) {
			return typeof(object).GetMembers(bindingAttr);
		}
		public override MethodInfo[] GetMethods(BindingFlags bindingAttr) {
			return typeof(object).GetMethods(bindingAttr);
		}
		protected override MethodInfo GetMethodImpl(string name, BindingFlags bindingAttr, Binder binder, CallingConventions callConvention, Type[] types, ParameterModifier[] modifiers) {
			return null;
		}
		public override Type GetNestedType(string name, BindingFlags bindingAttr) {
			return null;
		}
		public override Type[] GetNestedTypes(BindingFlags bindingAttr) {
			return null;
		}
		public override PropertyInfo[] GetProperties(BindingFlags bindingAttr) {
			return null;
		}
		protected override PropertyInfo GetPropertyImpl(string name, BindingFlags bindingAttr, Binder binder, Type returnType, Type[] types, ParameterModifier[] modifiers) {
			return null;
		}

		public override Type GetInterface(string name, bool ignoreCase) {
			return null;
		}
		public override Type[] GetInterfaces() {
			return null;
		}


		// Array stuff
		public override Type GetElementType() {
			return null;
		}
		protected override bool HasElementTypeImpl() {
			return false;
		}
	}

	public class NumericPseudoType: PseudoType, System.Runtime.Serialization.ISerializable {
		public NumericPseudoType(string name, TypePredicate predicate, SubTypePredicate subTypePredicate, SuperTypePredicate superTypePredicate) {
			this.name = name;
			this.predicate = predicate;
			this.subTypePredicate = subTypePredicate;
			this.superTypePredicate = superTypePredicate;
		}

		void System.Runtime.Serialization.ISerializable.GetObjectData(System.Runtime.Serialization.SerializationInfo info, System.Runtime.Serialization.StreamingContext context) {
			info.AddValue("name", name);
			info.SetType(typeof(PseudoTypeRef));
		}

		// Identity stuff
		string name;
		public override string Name {
			get {
				return name;
			}
		}
		public override string FullName {
			get {
				return myNamespace+"."+name;
			}
		}

		public delegate bool TypePredicate(object o);
		public TypePredicate predicate;

		public delegate bool SubTypePredicate(Type t);
		public SubTypePredicate subTypePredicate;

		public delegate bool SuperTypePredicate(Type t);
		public SuperTypePredicate superTypePredicate;

		// Type testing
		public override bool IsAssignableFrom(Type c) {
			return subTypePredicate(c);
		}
		public override bool IsInstanceOfType(object o) {
			return predicate(o);
		}

		public override bool IsSubclassOf(Type c) {
			return c==typeof(object) || superTypePredicate(c);
		}

		public override string ToString() {
			return Name;
		}
	}


	public interface ITypeExpression {
		bool SimpleBound(TypeVariable v, string message, Expression site);
		bool Instantiate(TypeVariable v, string message, Hashtable bindingEnvironment, Expression site);
	}


	//
	// Represents the Least Upper Bound of a set of types
	//
	public class LUBType : PseudoType, ITypeExpression, IPrettyPrintableType {
		public LUBType(IList bounds) {
			Procedure refiner = new Refiner(this);

			this.bounds = new ArrayList(bounds);
			foreach (object o in bounds) {
				if (o is TypeVariable)
					((TypeVariable)o).AddRefinementHandler(refiner);
			}
			Update();
		}

		bool ITypeExpression.Instantiate(TypeVariable v, string message, Hashtable bindingEnvironment, Expression site) {
			bool refined=false;

			if (v.currentType==null ||  v.currentType==typeof(object)) {
				object[] newbounds = new object[bounds.Count];
				for (int i=0; i<bounds.Count; i++) {
					object bound = bounds[i];
					if (bound is TypeVariable) {
						if (bindingEnvironment.ContainsKey(bound))
							newbounds[i] = bindingEnvironment[bound];
						else {
							TypeVariable n = new TypeVariable();
							n.Bound((TypeVariable)bound, message, bindingEnvironment, site);
							bindingEnvironment[bound] = n;
							newbounds[i] = n;
							//newbounds[i] = bound;
						}
					} else
						newbounds[i] = bound;
				}
				v.currentType=new LUBType(newbounds);
			} else {
				// It's already bound to something more complicated than an object...
				refined |= v.Bound(Type, message, bindingEnvironment, site);
			}
			return refined;
		}

		bool ITypeExpression.SimpleBound(TypeVariable v, string message, Expression site) {
			return false;
		}

		// Removes occurances of type variables that are equated to type variables already in the list or equated to ourselves.
		protected void Prune() {
			TypeVariable me = (typeVar!=null)?typeVar.Representative:null;
			int i=0;
			while (i<bounds.Count) {
				TypeVariable v = bounds[i] as TypeVariable;
				if (v!=null) {
					v = v.Representative;
					if (v==me)
						bounds.RemoveAt(i);
					else if (v.Type!=null && v.Type is LUBType) {
						bounds.RemoveAt(i);
						bounds.AddRange(((LUBType)v.Type).bounds);
					} else {
						// Check if it's already there.
						bool found=false;
						for (int j=0; j<i && !found; j++) {
							if (bounds[j]==v)
								found=true;
						}
						if(found)
							bounds.RemoveAt(i);
						else {
							bounds[i]=v;
							i++;
						}
					}
				} else
					i++;
			}
		}

		public ArrayList bounds;
		protected Type currentType;
		protected LUBTypeVariable typeVar;

		public Type Type {
			get {
				return currentType;
			}
		}

		public TypeVariable AsTypeVariable {
			get {
				if (typeVar==null)
					typeVar = new LUBTypeVariable(this);
				return typeVar;
			}
		}

		public virtual void Update() {
			Prune();
			Type oldType = currentType;
			currentType = TypeLattice.LUB(bounds);
			if (TypeVariable.TraceRefinement)
				TopLevel.Log("LUBType.Update", this, oldType,"to", currentType);
			if (oldType!=currentType && typeVar!=null)
				typeVar.RefineHandler(this);
		}

		protected class Refiner : CallInterfaceProcedure {
			LUBType typeToBeRefined;
			public Refiner(LUBType t) {
				typeToBeRefined = t;
			}

			public override object Call() {
				typeToBeRefined.Update();
				return null;
			}
		}

		protected class LUBTypeVariable : TypeVariable {
			public LUBTypeVariable(Type t) : base(t, null) {}

			// This just exposed refine to LUBType.
			public void RefineHandler(Type t) {
				if (TypeVariable.TraceRefinement)
					TopLevel.Log("LUBTypeVariable.RefineHandler: refining");
				Refine(t, null, null);
			}
			public override bool Bound(TypeVariable bound, string message, Hashtable bindingEnvironment, Expression site) {
				throw new Exception("Can't further bound a LUB Type variable");
			}

			public override bool Bound(Type t, string message, Hashtable bindingEnvironment, Expression site) {
				throw new Exception("Can't further bound a LUB Type variable");
			}
		}

		public override string Name {
			get {
				return "LUBType/"+currentType.ToString();
			}
		}

		public override string FullName {
			get {
				return "Meta.LUBType";
			}
		}

		public override bool IsSubclassOf(Type c) {
			return currentType.IsSubclassOf (c);
		}

		public override bool IsAssignableFrom(Type c) {
			return currentType.IsAssignableFrom (c);
		}

		public override string ToString() {
			//Update();  this causes the trace window to loop
			return ((IPrettyPrintableType)this).PrettyPrint(TypeWalker.NameTypes(this));
		}

		string IPrettyPrintableType.PrettyPrint(Hashtable h) {
			// We preprocess the list of bounds to remove ones that are redundant, but we make sure we keep
			// the ones that show up as parametric types.
			ArrayList typeVars = new ArrayList();

			// Overall LUB of all bounds that are not named type variables within the expression we're pretty-printing.
			Type otherBounds = null;

			// Check each bound to see if it's a named type variable
			//   yes => put it into typeVars
			//   no => incorporate it into other-bounds.
			foreach (object bound in bounds) {
				if (bound is Type)
					otherBounds = TypeLattice.LUB((Type)bound, otherBounds);
				else {
					TypeVariable v = ((TypeVariable)bound).Representative;
					if (h.ContainsKey(v)) {
						if (!typeVars.Contains(v))
							typeVars.Add(v);
					} else
						otherBounds = (otherBounds==null)?v.Type:TypeLattice.LUB(v.Type, otherBounds);
				}
			}

			// If we have some "constant" bounds (relative to the expression we're pretty-printing)
			// Prune any of the type variables from typeVars that are already subtypes of the constant bounds.
			if (otherBounds!=null) {
				int ti = 0;
				while (ti<typeVars.Count) {
					TypeVariable v = typeVars[ti] as TypeVariable;
					if (v==null || TypeLattice.SubType(v.Type, otherBounds) || v.Type==otherBounds)
						// This type can't ever affect the LUB
						typeVars.RemoveAt(ti);
					else
						ti++;
				}
			}

			// If no typeVars; print the otherBounds
			if (otherBounds!=null && typeVars.Count==0)
				return otherBounds.ToString();
			// If only a type var, print that.
			else if (otherBounds==null && typeVars.Count==1) {
				return ((IPrettyPrintableType)typeVars[0]).PrettyPrint(h);
			// Otherwise print a type expression
			} else {
				StringBuilder sb = new StringBuilder();
				sb.Append("[LUB ");
				bool firstone=true;
				foreach (object o in typeVars) {
					if (firstone)
						firstone = false;
					else
						sb.Append(" ");
					if (o is IPrettyPrintableType)
						sb.Append(((IPrettyPrintableType)o).PrettyPrint(h));
					else
						sb.Append(o.ToString());
				}
				if (otherBounds!=null) {
					// Note: Can't be firstone
					sb.Append(" ");
					if (otherBounds is IPrettyPrintableType)
						sb.Append(((IPrettyPrintableType)otherBounds).PrettyPrint(h));
					else
						sb.Append(otherBounds.ToString());
				}
				sb.Append("]");
				return sb.ToString();
			}
		}
	}

	//
	// Represents the Least Upper Bound of arguments used in arithmetic.
	//
	public class ArithmeticLUBType : LUBType {
		public ArithmeticLUBType(IList bounds) : base(bounds) { }

		public override void Update() {
			Prune();
			Type oldType = currentType;
			ArrayList nonNumeric = new ArrayList();
			foreach (TypeVariable v in bounds) {
				if (TypeLattice.IsArithmeticTypeInclusive(v.Type) && !TypeLattice.IsNumericType(v.Type))
					nonNumeric.Add(v);
			}
			currentType = TypeLattice.LUB((nonNumeric.Count>0)?nonNumeric:bounds);
			if (TypeVariable.TraceRefinement)
				TopLevel.Log("ArithmeticLUBType.Update", this, oldType,"to", currentType);
			if (oldType!=currentType && typeVar!=null)
				typeVar.RefineHandler(this);
		}
	}

	public class ListOf : PseudoType, ITypeExpression, IPrettyPrintableType {
		public TypeVariable ItemType;
		public ListOf(Type t) : this(new TypeVariable(t, null)) {}
		public ListOf(TypeVariable ItemType) {
			this.ItemType = ItemType;
		}

		bool ITypeExpression.Instantiate(TypeVariable v, string message, Hashtable bindingEnvironment, Expression site) {
			bool refined = false;

			// Ensure the variable is a ListOf
			ListOf dest = (v.currentType==null)?null:(v.currentType as ListOf);
			if (dest==null) {
				refined = true;
				v.currentType = dest = new ListOf(new TypeVariable(typeof(object), v.expression));
			}
			// Unify the element types
			refined |= TypeVariable.Instantiate(dest.ItemType, ItemType, message, bindingEnvironment, site);
			return refined;
		}

		bool ITypeExpression.SimpleBound(TypeVariable v, string message, Expression site) {
			return false;
		}

		public override string Name {
			get {
				return string.Format("ListOf<{0}>", ItemType.Type.Name);
			}
		}

		public override string FullName {
			get {
				return "Meta."+Name;
			}
		}

		public override string ToString() {
			return ((IPrettyPrintableType)this).PrettyPrint(TypeWalker.NameTypes(this));
		}

		string IPrettyPrintableType.PrettyPrint(Hashtable h) {
			return string.Format("[list-of {0}]", ((IPrettyPrintableType)ItemType).PrettyPrint(h));
		}

		public override MemberInfo[] GetMember(string name, BindingFlags bindingAttr) {
			return typeof(ArrayList).GetMember (name, bindingAttr);
		}

		public override MemberInfo[] GetMember(string name, MemberTypes type, BindingFlags bindingAttr) {
			return typeof(ArrayList).GetMember (name, type, bindingAttr);
		}

		public override MemberInfo[] GetMembers(BindingFlags bindingAttr) {
			return typeof(ArrayList).GetMembers(bindingAttr);
		}

		public override MethodInfo[] GetMethods(BindingFlags bindingAttr) {
			return typeof(ArrayList).GetMethods(bindingAttr);
		}

		public override PropertyInfo[] GetProperties(BindingFlags bindingAttr) {
			return typeof(ArrayList).GetProperties(bindingAttr);
		}
	}

	public abstract class ProcedureType : PseudoType {
		public static Type ParseProcedureTypeExpression(IList exp) {
			if (exp[exp.Count-2]!=Symbol.sLambdaArrow)
				throw new SyntaxError("Malformed procedure type expression", exp);
			Type resultType = Parser.ParseTypeExpression(exp[exp.Count-1]);
			TypeVariable[] argTypes = new TypeVariable[exp.Count-2];
			for (int i=0; i<argTypes.Length; i++)
				argTypes[i] = new TypeVariable(Parser.ParseTypeExpression(exp[i]), null);
			return new SimpleProcedureType(new TypeVariable(resultType, null), argTypes, null, argTypes.Length, 0, -1, false, new TypeVariable());
		}

		public override Type BaseType {
			get {
				return typeof(Meta.Procedure);
			}
		}

		public override string Name {
			get {
				return this.GetType().Name;
			}
		}

		public override string FullName {
			get {
				return "ProcedureType";
			}
		}


		// Boilerplate
		public override Guid GUID {
			get {
				return new Guid ();
			}
		}

		protected override TypeAttributes GetAttributeFlagsImpl() {
			return TypeAttributes.Abstract;
		}
		protected override bool IsArrayImpl() {
			return false;
		}
		protected override bool IsByRefImpl() {
			return true;
		}
		protected override bool IsCOMObjectImpl() {
			return false;
		}
		protected override bool IsPointerImpl() {
			return false;
		}
		protected override bool IsPrimitiveImpl() {
			return false;
		}
		public override RuntimeTypeHandle TypeHandle {
			get {
				return new RuntimeTypeHandle ();
			}
		}
		public override Type UnderlyingSystemType {
			get {
				return typeof(object);  // ???
			}
		}

		public override bool IsAssignableFrom(Type c) {
			return this.GetType()==c.GetType();
		}


		public override object InvokeMember(string name, BindingFlags invokeAttr, Binder binder, object target, object[] args, ParameterModifier[] modifiers, System.Globalization.CultureInfo culture, string[] namedParameters) {
			throw new MissingMemberException(FullName, name);
		}

		//
		// PseudoTypes aren't real classes, so none of the following operations make any sense.
		// However, we have to have implementations of them to get things to compile.
		//

		// Assembly stuff
		public override Assembly Assembly {
			get {
				return null;
			}
		}
		public override string AssemblyQualifiedName {
			get {
				return null;
			}
		}
		public override Module Module {
			get {
				return null;
			}
		}
		public override string Namespace {
			get {
				return "Meta.";
			}
		}

		// Attribute stuff
		public override object[] GetCustomAttributes(bool inherit) {
			return null;
		}
		public override object[] GetCustomAttributes(Type attributeType, bool inherit) {
			return null;
		}
		public override bool IsDefined(Type attributeType, bool inherit) {
			return false;
		}

		// Member stuff
		protected override ConstructorInfo GetConstructorImpl(BindingFlags bindingAttr, Binder binder, CallingConventions callConvention, Type[] types, ParameterModifier[] modifiers) {
			return null;
		}
		public override ConstructorInfo[] GetConstructors(BindingFlags bindingAttr) {
			return null;
		}
		public override EventInfo GetEvent(string name, BindingFlags bindingAttr) {
			return null;
		}
		public override EventInfo[] GetEvents(BindingFlags bindingAttr) {
			return null;
		}
		public override FieldInfo GetField(string name, BindingFlags bindingAttr) {
			return null;
		}
		public override FieldInfo[] GetFields(BindingFlags bindingAttr) {
			return null;
		}
		public override MemberInfo[] GetMember(string name, BindingFlags bindingAttr) {
			return base.GetMember (name, bindingAttr);
		}
		public override MemberInfo[] GetMembers(BindingFlags bindingAttr) {
			return new MemberInfo[0];
		}
		public override MethodInfo[] GetMethods(BindingFlags bindingAttr) {
			return new MethodInfo[0];
		}
		protected override MethodInfo GetMethodImpl(string name, BindingFlags bindingAttr, Binder binder, CallingConventions callConvention, Type[] types, ParameterModifier[] modifiers) {
			return null;
		}
		public override Type GetNestedType(string name, BindingFlags bindingAttr) {
			return null;
		}
		public override Type[] GetNestedTypes(BindingFlags bindingAttr) {
			return new Type[0];
		}
		public override PropertyInfo[] GetProperties(BindingFlags bindingAttr) {
			return new PropertyInfo[0];
		}
		protected override PropertyInfo GetPropertyImpl(string name, BindingFlags bindingAttr, Binder binder, Type returnType, Type[] types, ParameterModifier[] modifiers) {
			return null;
		}

		public override Type GetInterface(string name, bool ignoreCase) {
			return null;
		}
		public override Type[] GetInterfaces() {
			return new Type[0];
		}


		// Array stuff
		public override Type GetElementType() {
			return null;
		}
		protected override bool HasElementTypeImpl() {
			return false;
		}
	}


	public class SimpleProcedureType : ProcedureType, ITypeExpression, IPrettyPrintableType {
		public TypeVariable resultType;
		public IList argTypes;
		public Meta.Expression lambda;
		public int requiredArgs;
		public int optionalArgs;
		public int keywordStart;
		public bool hasRestArg;
		public TypeVariable restArgType;

		public SimpleProcedureType(TypeVariable ResultType, IList ArgTypes, Meta.Expression lambda,
													int requiredArgs, int optionalArgs, int keywordStart,
													bool hasRestArg, TypeVariable restArgType) {
			this.resultType = ResultType;
			this.argTypes = ArgTypes;
			this.lambda = lambda;
			this.requiredArgs = requiredArgs;
			this.optionalArgs = optionalArgs;
			this.keywordStart = keywordStart;
			this.hasRestArg = hasRestArg;
			this.restArgType = restArgType;
		}


		bool ITypeExpression.Instantiate(TypeVariable v, string message, Hashtable bindingEnvironment, Expression site) {
			bool refined=false;

			SimpleProcedureType dest = (v.currentType==null)?null:(v.currentType as SimpleProcedureType);
			if (dest == null) {
				refined = true;
				TypeVariable[] args = new TypeVariable[argTypes.Count];
				for (int a=0; a<args.Length; a++)
					args[a] = new TypeVariable();
				v.currentType = dest = new SimpleProcedureType(new TypeVariable(), args, v.expression, requiredArgs, optionalArgs, keywordStart, hasRestArg, new TypeVariable());
			}
			refined |= TypeVariable.Instantiate(dest.resultType, resultType, message, bindingEnvironment, site);
			refined |= TypeVariable.Instantiate(dest.restArgType, restArgType, message, bindingEnvironment, site);
			int matchargs= dest.requiredArgs+dest.optionalArgs;
			if (matchargs>requiredArgs+optionalArgs) {
				matchargs = requiredArgs+optionalArgs;
				if (matchargs<dest.requiredArgs)
					TypeVariable.Warn("Wrong number of arguments", v.expression, "procedure types have incompatible numbers of arguments", site);
			} else if (matchargs<requiredArgs)
				TypeVariable.Warn("Wrong number of arguments", v.expression, "procedure types have incompatible numbers of arguments", site);;
			for (int i=0; i<matchargs; i++)
				refined |= TypeVariable.Instantiate((TypeVariable)dest.argTypes[i], (TypeVariable)argTypes[i], message, bindingEnvironment, site);

			return refined;
		}

		bool ITypeExpression.SimpleBound(TypeVariable v, string message, Expression site) {
			return false;
		}

		public override string ToString() {
			Hashtable h = TypeWalker.NameTypes(this);
			return ((IPrettyPrintableType)this).PrettyPrint(h);
		}

		string IPrettyPrintableType.PrettyPrint(Hashtable h) {
			System.Text.StringBuilder b = new System.Text.StringBuilder();
			b.Append("[");
			bool firstone=true;
			foreach (object a in argTypes) {
				if (firstone)
					firstone = false;
				else
					b.Append(" ");
				if (a!=null ) {
					b.Append(((IPrettyPrintableType)a).PrettyPrint(h));
				} else
					b.Append("notAType");
			}
			b.Append(" \u2192 ");
			b.Append(((IPrettyPrintableType)resultType).PrettyPrint(h));
			b.Append("]");
			return b.ToString ();
		}

	}

	[Serializable]
	public class PseudoTypeRef : System.Runtime.Serialization.IObjectReference {
		public PseudoTypeRef(String nameArg)  {
			name=nameArg;
		}
		public String name;
		object System.Runtime.Serialization.IObjectReference.GetRealObject(System.Runtime.Serialization.StreamingContext context) {
			switch (name) {
				case "Arithmetic":
					return PseudoType.Arithmetic;

				case "Number":
					return PseudoType.Number;

				case "Integer":
					return PseudoType.Integer;

				case "Integral":
					return PseudoType.Integral;

				case "Float":
					return PseudoType.Float;

				case "Vector":
					return PseudoType.Vector;

				case "Vector2D":
					return PseudoType.Vector2D;

				default:
					throw new TypeLoadException("Unknown PseudoType "+name);
			}
		}
	}


}
